{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "0187cfb0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "公钥 (p, g, y): (1069, 1066, 161)\n",
      "私钥 x: 688\n",
      "消息明文: 123\n",
      "密文: (749, 105)\n",
      "解密还原明文: 123\n"
     ]
    }
   ],
   "source": [
    "## ElGamal Algorithm\n",
    "\n",
    "from random import randint\n",
    "from sympy import isprime, mod_inverse\n",
    "\n",
    "def generate_keys():\n",
    "    # Generate the prime number p and the primitive root g\n",
    "    while True:\n",
    "        p = randint(1000, 2000)\n",
    "        if isprime(p):\n",
    "            break\n",
    "    g = randint(2, p-1)\n",
    "\n",
    "    # private key x\n",
    "    x = randint(1, p-2)\n",
    "    \n",
    "    # public key y\n",
    "    y = pow(g, x, p)\n",
    "\n",
    "    return (p, g, y), x\n",
    "\n",
    "def encrypt(public_key, message):\n",
    "    p, g, y = public_key\n",
    "    k = randint(1, p-2)\n",
    "\n",
    "    # encryption\n",
    "    C1 = pow(g, k, p)\n",
    "    C2 = (message * pow(y, k, p)) % p\n",
    "\n",
    "    return (C1, C2)\n",
    "\n",
    "def decrypt(private_key, p, ciphertext):\n",
    "    C1, C2 = ciphertext\n",
    "    a = private_key\n",
    "\n",
    "    # decryption\n",
    "    s = pow(C1, a, p)\n",
    "    m = (C2 * mod_inverse(s, p)) % p\n",
    "\n",
    "    return m\n",
    "\n",
    "# Example\n",
    "public_key, private_key = generate_keys() # Generate the keys\n",
    "message = 123  # Plaintext message\n",
    "ciphertext = encrypt(public_key, message) # Ciphertext\n",
    "decrypted_message = decrypt(private_key, public_key[0], ciphertext) # Decrypt\n",
    "\n",
    "print(\"Public key (p, g, y):\", public_key)\n",
    "print(\"Private key x:\", private_key)\n",
    "print(\"Plaintext message:\", message)\n",
    "print(\"Ciphertext:\", ciphertext)\n",
    "print(\"Decrypted plaintext message:\", decrypted_message)\n",
    "\n",
    "## Output Example\n",
    "# Public key (p, g, y): (1307, 643, 698)\n",
    "# Private key x: 11\n",
    "# Plaintext message: 123\n",
    "# Ciphertext: (690, 1225)\n",
    "# Decrypted plaintext message: 123\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "8e578d36",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "公钥 (p, g, y): (1409, 853, 1193)\n",
      "私钥 x: 1035\n",
      "消息明文: 123\n",
      "签名: (1126, 1403)\n",
      "验证结果: True\n"
     ]
    }
   ],
   "source": [
    "## ElGamal 签名算法\n",
    "\n",
    "from sympy import gcd\n",
    "\n",
    "def generate_keys_signature():\n",
    "    # 和 ElGamal 加密算法一样\n",
    "    return generate_keys()\n",
    "\n",
    "def sign(private_key, p, g, message):\n",
    "    while True:\n",
    "        k = randint(1, p-1)\n",
    "        if gcd(k, p-1) == 1:  # k 与 p-1 互质\n",
    "            break\n",
    "\n",
    "    r = pow(g, k, p)\n",
    "    x = private_key\n",
    "    s = ((message - x * r) * mod_inverse(k, p-1)) % (p-1)\n",
    "\n",
    "    return (r, s)\n",
    "\n",
    "def verify(public_key, p, g, message, signature):\n",
    "    y = public_key[2]\n",
    "    r, s = signature\n",
    "\n",
    "    if not (0 < r < p) or not (0 < s < p-1):\n",
    "        return False\n",
    "\n",
    "    return pow(g, message, p) == (pow(y, r, p) * pow(r, s, p)) % p\n",
    "\n",
    "# 示例\n",
    "public_key, private_key = generate_keys_signature() # 生成密钥\n",
    "message = 123  # 消息明文\n",
    "signature = sign(private_key, public_key[0], public_key[1], message) # 生成签名\n",
    "verification_result = verify(public_key, public_key[0], public_key[1], message, signature) # 验证签名\n",
    "\n",
    "public_key, private_key, signature, verification_result\n",
    "\n",
    "print(\"公钥 (p, g, y):\", public_key)\n",
    "print(\"私钥 x:\", private_key)\n",
    "print(\"消息明文:\", message)\n",
    "print(\"签名:\", signature)\n",
    "print(\"验证结果:\", verification_result)\n",
    "\n",
    "## 输出样例\n",
    "# 公钥 (p, g, y): (1409, 853, 1193)\n",
    "# 私钥 x: 1035\n",
    "# 消息明文: 123\n",
    "# 签名: (1126, 1403)\n",
    "# 验证结果: True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "36ab833e",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
